Permutación de Stirling

En combinatoria, una permutación de Stirling de orden k es una permutación del multiconjunto 1, 1, 2, 2, ..., k, k (con dos copias de cada valor de 1 a k) con la propiedad añadida de que, por cada valor i que aparece en la permutación, los valores entre las dos copias de i son mayores que i. Por ejemplo, las 15 permutaciones de Stirling de orden tres son

1,1,2,2,3,3;   1,2,2,1,3,3;   2,2,1,1,3,3;

1,1,2,3,3,2;   1,2,2,3,3,1;   2,2,1,3,3,1;

1,1,3,3,2,2;   1,2,3,3,2,1;   2,2,3,3,1,1;

1,3,3,1,2,2;   1,3,3,2,2,1;   2,3,3,2,1,1;

3,3,1,1,2,2;   3,3,1,2,2,1;   3,3,2,2,1,1.

El número de permutaciones de Stirling de orden k está dado por el doble factorial (2k − 1)!!. Las permutaciones de Stirling fueron introducidas por Gessel y Stanley (1978) para demostrar que ciertos números (los números de las permutaciones de Stirling con un número fijo de descendentes) son no-negativos. Eligieron el nombre a causa de una conexión a ciertos polinomios definidos por los números de Stirling, que se llamaron así después del siglo XVII en honor al matemático escocés James Stirling.​

Construcción de una permutación de Stirling a partir de una torre de Euler de un árbol plano con sus aristas ordenadas por orden de construcción.

Las permutaciones de Stirling pueden usarse para describir las secuencias por las cuales es posible construir un árbol plano arraigado con k bordes añadiendo hojas una por una al árbol. Si los bordes están numerados por el orden en que fueron insertados, entonces la secuencia de números en una torre de Euler del árbol (formada al doblar los bordes del árbol y atravesar a los descendientes de cada nodo de izquierda a derecha) es una permutación de Stirling. Por el contrario, cada permutación de Stirling describe una secuencia de construcción de árbol, en la cual el siguiente borde más cercano a la raíz de un borde ordenado i es aquel cuyo par de valores rodea más estrechamente al par de valores i en la permutación.

Las permutaciones de Stirling se han generalizado a las permutaciones de un multiconjunto con más de dos copias de cada valor. Los investigadores también han estudiado el número de permutaciones de Stirling que evitan ciertos patrones.​

Véase también

• Emparejamiento de Langford, otro tipo de permutación del mismo multiconjunto.

Referencias

• Datos: Q17103734